package 动态规划.另类的;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/5 14:14
 */
public class lc647回文子串 {

    /*
     先采用切割的思想.来做这道题!
     - 切割的思想是不对的, 对于该题来说,因为计算的是 ,s 的 回文子串的个数,
     eg: aabbbb    a| a| bbbb 和  aa| bbbb 这两种情况的时候, 其实 bbbb 已经重复计算了, 这就是错误的原因!
     但是 对于 **131 题目** 来说 切割就是正确的, 注意题目的要求不一样!
     */
    public int recursion(int index, String s) {
        if (index == s.length()) {
            return 0;
        }
        int ans = 0;
        for (int i = index; i < s.length(); i++) {
            if (isValid(index, i, s.toCharArray())) {
                ans += recursion(i + 1, s) + 1;
            }
        }
        return ans;
    }

    public boolean isValid(int s, int e, char[] str) {
        for (int i = s, j = e; i < j; i++, j--) {
            if (str[i] != str[j]) {
                return false;
            }
        }
        return true;
    }

    /*
    131 这个题,直接 提供了一个 巨大的思路, dp[i][j] 配合 切割的做法,
    可以先把 dp[i][j]的缓存表给填好!
    - 一个 隐含的条件 i <=j , 也就是 对角线一下的 值,没有任何的意义
     */

    public void recursion(int index, String s, Boolean[][] dp) {
        if (index == s.length()) {
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (dp[index][i] == null) {
                dp[index][i] = isValid(index, i, s.toCharArray());
                recursion(i + 1, s, dp);
            }
        }
    }

    // 2688ms  马马虎虎能过
    public int solution(String s) {
        Boolean dp[][] = new Boolean[s.length()][s.length()];
        recursion(0, s, dp);
        int ans = 0;
        for (Boolean[] booleans : dp) {
            for (Boolean b : booleans) {
                if (b != null && b) {
                    ans++;
                }
            }
        }
        return ans;
    }

    /*
     动态规划的 写法:
     先把 函数 给出来:
     - 回文子串, 天然 具有 状态转移的 性质:  f(i,j) 函数的 含义 , 是至关重要的!
     f(i, j) : 表示的是  s[i,j] 是不是 回文子串, 仅表示  s[i, j] 是不是回文子串
     s[i] != s[j]  ----> f(i,j ) 直接 false
     */

    /*
     看着 这个函只能 单独 计算 f(i, j )
     但是改成 dp 之后,就不一样了!
     */
    public boolean f(int i, int j, String s) {
        if (i > j) {
            return false;
        }
        if (s.charAt(i) == s.charAt(j)) {
            if (j - i <= 2 || f(i + 1, j - 1, s)) {  // a   aa   axa 包含这三种情况 ,这些都是回文串 , 以及如果 f(i + 1, j - 1) 也是 回文串, 那当前就是 回文串!
                return true;
            }
        }

        return false;
    }


    /*
     将上面的 f 函数 改成 dp
     其中 i : 0 ~ len - 1
        j  : i ~ len - 1;  // j >= i , 这一点显而易见!
     */
    public int dp(String s) {
        boolean dp[][] = new boolean[s.length()][s.length()];
        int ans = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        ans++;
                    }
                }
            }
        }
        return ans;
    }


}
